#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int merge(int *p, int l, int mid, int r) {
  int ans = 0;
  int *q = new int[r - l + 1];
  int lc = l;
  int rc = mid + 1;
  int count = 0;
  while (lc <= mid && rc <= r) {
    if (p[lc] < p[rc]) {
      ans += (r - rc + 1) * p[lc];
      q[count] = p[lc];
      ++lc;
    } else {
      q[count] = p[rc];
      ++rc;
    }
    ++count;
  }
  while (lc <= mid) {
    q[count] = p[lc];
    ++lc;
    ++count;
  }
  while (rc <= r) {
    q[count] = p[rc];
    ++rc;
    ++count;
  }
  for (int i = 0; i < count; ++i) {
    p[l + i] = q[i];
  }
  return ans;
}

int smallsum(int *p, int l, int r) {
  if (l >= r) {
    return 0;
  }
  int m = l + ((r - l) >> 1);
  int ans1 = smallsum(p, l, m);
  int ans2 = smallsum(p, m + 1, r);
  int ans3 = merge(p,l,m,r);
  return ans1+ans2+ans3;
}

int main() {}
